package jianzhioffer;

import java.util.Arrays;

/**
 * Author: Zhang Dongwei
 * Date: 2023/3/28 10:46
 * 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
 */
public class offer_66_构建乘积数组 {

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5};
        int[] b = new int[a.length];
        System.out.println(Arrays.toString(constructArr(a)));
    }

//    暴力双重循环，超时
    public static int[] constructArr1(int[] a) {
        int[] b = new int[a.length];
        for (int i=0; i<a.length; i++){
            b[i]=1;
            for (int j=0; j<a.length; j++){
                if (i==j) continue;
                else b[i] *= a[j];
            }
        }
        return b;
    }

//    上下三角题解(不太好理解)
    public static int[] constructArr2(int[] a) {
        int len = a.length;
        if (len==0) return new int[0];
        int[] b = new int[len];
        b[0]=1;
        int tem = 1;
        for (int i=1; i<len; i++){
            b[i] = b[i-1] * a[i-1];
        }
        for (int i = len-2; i>=0; i--){
            tem *= a[i+1];
            b[i] *= tem;
        }
        return b;
    }

//    保存两个数组，左右相乘(稍微好理解一点),本质和上面的类似
    public static int[] constructArr(int[] a) {
        int len = a.length;
        if (a.length<=1) return a;
        int[] left = new int[len];
        int[] right = new int[len];
        int[] res = new int[len];
        left[0] = right[len-1] = 1;

        for (int i=1; i<len; i++){
            left[i] = left[i-1] * a[i-1];
        }
        for (int i=len-2; i>=0; i--){
            right[i] = right[i+1] * a[i+1];
        }
        for (int i=0; i<len; i++){
            res[i] = left[i] * right[i];
        }
        return res;
    }
}
